package DynamicProgrammingPackage;

public class maxProfitII_ {

    /**
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     *
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。
     *
     * 返回 你能获得的 最大 利润 。
     * dp[i][0]表示持有股票的最大金额, dp[i][1]表示不持有股票的最大金额
     * 递推公式: dp[i][0] =Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]), dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][1] + prices[i])
     * 多次买卖, 买入股票时, 其金额不是-prices
     */
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
    }
}
